package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * aab 如何分割使得子串都是回文串
 * 方式1： aa  b
 * 方式2:  a  a  b
 *
 * 和组合问题类似：
 * 比如先分割了a，那么下来就在ab里面分割
 *
 *             aab
 *    截取a            截取第二个a        切割b
 *    a|ab               aa|b             aab|
 *     ab                b
 *
 * 截取a  切割b          切割b
 * a|a|b  a|ab|          aa|b|
 *   b
 *
 * 截取b
 * a|a|b|
 *
 *
 */
public class a09_分割回文串 {

    public static void main(String[] args) {
        a09_分割回文串 test = new a09_分割回文串();
        List<List<String>> aab = test.partition("aab");
        System.out.println(aab);
    }

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        LinkedList<String> path = new LinkedList<>();
        char[] chars = s.toCharArray();
        traversal(result, path, chars, 0);
        return result;
    }

    private void traversal(List<List<String>> result,
                           LinkedList<String> path,
                           char[] chars,
                           int startIdx
                           ){
        if(startIdx == chars.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIdx; i < chars.length; i++) {
            if (!check(chars,startIdx,i)) {
                continue;
            }
            path.add(splitArray(chars, startIdx,i));
            traversal(result, path, chars, i + 1);
            path.removeLast();
        }
    }

    private boolean check(char[] chars,int leftIdx,int rightIdx){
        while (leftIdx < rightIdx) {
            if(chars[leftIdx] != chars[rightIdx]){
                return false;
            }
            leftIdx++;
            rightIdx--;
        }
        return true;
    }

    private String splitArray(char[] chars,int leftIdx,int rightIdx){
        StringBuilder sb = new StringBuilder();
        while (leftIdx <= rightIdx) {
            sb.append(chars[leftIdx]);
            leftIdx++;
        }
        return sb.toString();
    }
}
